package com.jack.leetcode.每日一题;

import java.util.ArrayList;
import java.util.List;

/***
 * @author zhangjie
 * @date 2020/4/9 20:01
 */
public class 括号生成 {

    public static void main(String[] args) {
        int n = 3;
        List<String> l = generateParenthesis(n);
        l.stream().forEach(s-> System.out.println(s));
    }

    public static List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        String s = "";
        dfs(s,n,n,result);
        return result;
    }

    private static void dfs(String s,int left,int right,List<String> result){
        if(left == 0 && right ==0){
            result.add(s);
            return;
        }
        if(left > right){
            return;
        }
        if(left > 0){
            dfs(s+"(",left-1,right,result);
        }
        if(right > 0){
            dfs(s+")",left,right-1,result);
        }

    }
}
